1. Field of the Invention
The present invention relates to the technical field of digital signal processing and, more particularly, to a fixed-coefficient variable prime length recursive discrete Fourier transform system.
2. Description of Related Art
With the rapid development of digital signal processing technique, users can conveniently obtain messages and enjoy various multimedia information in daily life, in which Discrete Fourier Transform (DFT) has been widely applied in various audio codec standards.
The hardware architecture of DFT can be divided into parallel architecture and recursive architecture. In comparison with the parallel architecture, the recursive architecture has drawbacks in having high computation cycle, lowering the precision degree due to increase of frame size, and negatively influencing the chip area due to coefficient-generated ROM. Therefore, there are several Recursive DFT (RDFT) methods proposed to reduce the computation cycle, complexity, and amount of coefficient required.
A method of computing DFT is proposed by taking a recursive architecture as its kernel (See Goertzel “An algorithm for the evaluation of finite trigonometric series”, American mathematical monthly, pp. 34-35, 1958). Further, a hardware architecture is also proposed, which requires N2 cycles to compute N points of DFT, while the overall hardware requires six adders and six multipliers (See Curtis & Wickenden “Hardware-based Fourier transforms: algorithms and architectures”, Radar and Signal Processing, IEE Proceedings F, vol. 130, pp. 423-432, 1983)
In Yang & Chen “Recursive discrete Fourier transform with unified IIR filter structures”, Elsevier Science B. V. Signal Process, vol. 82, pp. 31-41, 2002, a hardware architecture is also proposed that requires N2 cycles to compute N points of DFT, and the overall hardware requires twelve adders and six multipliers. Moreover, in Lai, Chang, Lin, & Luo “Low Computational Complexity, Low Power, and Low Area. Design for the Implementation of Recursive DFT and IDFT Algorithms” Circuits and Systems II: Express Briefs, IEEE Transactions on, vol. 56, pp. 921-925, 2009, the proposed hardware architecture requires 12 adders and two multipliers.
Even though the RDFT has been developed for several years, there is still a need to have an RDFT system capable of reducing the computation complexity, lowering the hardware cost, and increasing the data computation efficiency.